package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created by 朱城委 on 2022-1-15.<br><br>
 *
 * 中等：三角形最小路径和
 */
public class Topic120 {

    public static void main(String[] args) {
        BaseSolution solution = new Solution3();

        List<List<Integer>> list = new ArrayList<>();
        list.add(Collections.singletonList(2));
        list.add(Arrays.asList(3, 4));
        list.add(Arrays.asList(6, 5, 7));
        list.add(Arrays.asList(4, 1, 8, 3));
        System.out.println(solution.minimumTotal(list));

        list.clear();
        list.add(Collections.singletonList(-10));
        System.out.println(solution.minimumTotal(list));

        list.clear();
        list.add(Collections.singletonList(-1));
        list.add(Arrays.asList(2, 3));
        list.add(Arrays.asList(1, -1, -3));
        System.out.println(solution.minimumTotal(list));
    }

    private interface BaseSolution {
        int minimumTotal(List<List<Integer>> triangle);
    }

    /**
     * 递归解法，时间复杂度太高
     */
    private static class Solution1 implements BaseSolution {

        @Override
        public int minimumTotal(List<List<Integer>> triangle) {
            return helper(triangle, 0, 0);
        }

        private int helper(List<List<Integer>> triangle, int level, int index) {
            if(level >= triangle.size() || index >= triangle.get(level).size()) {
                return 0;
            }

            int temp = triangle.get(level).get(index);
            int result1 = temp + helper(triangle, level + 1, index);
            int result2 = temp + helper(triangle, level + 1, index + 1);

            return Math.min(result1, result2);
        }
    }

    /**
     * 动态规划解法，空间空间复杂度O(n^2)
     */
    private static class Solution2 implements BaseSolution {

        @Override
        public int minimumTotal(List<List<Integer>> triangle) {
            int n = triangle.size();
            int[][] array = new int[n][n];
            array[0][0] = triangle.get(0).get(0);

            for(int i = 1; i < n; i++) {
                array[i][0] = array[i - 1][0] + triangle.get(i).get(0);

                for(int j = 1; j < i; j++) {
                    array[i][j] = Math.min(array[i - 1][j - 1], array[i - 1][j]) + triangle.get(i).get(j);
                }

                array[i][i] = array[i - 1][i - 1] + triangle.get(i).get(i);
            }

            int result = array[n - 1][0];
            for(int i = 1; i < n; i++) {
                result = Math.min(result, array[n - 1][i]);
            }

            return result;
        }
    }

    /**
     * 动态规划解法，空间空间复杂度O(n)
     */
    private static class Solution3 implements BaseSolution {

        @Override
        public int minimumTotal(List<List<Integer>> triangle) {
            int n = triangle.size();
            int[] array = new int[n];
            array[0] = triangle.get(0).get(0);

            for(int i = 1; i < n; i++) {
                array[i] = array[i - 1] + triangle.get(i).get(i);

                for(int j = i - 1; j > 0; j--) {
                    array[j] = Math.min(array[j - 1], array[j]) + triangle.get(i).get(j);
                }

                array[0] = array[0] + triangle.get(i).get(0);
            }

            int result = array[0];
            for(int i = 1; i < n; i++) {
                result = Math.min(result, array[i]);
            }

            return result;
        }
    }
} 
